﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Rotate90Degrees
{
    class Program
    {
        static void Main(string[] args)
        {
            int m = 4;
            int n = 4;

            int[,] input = new int[m, n];
            input= Initialize(input);
            Display(input);

            Console.WriteLine();
            Console.WriteLine("Rotating Matrix 90 degrees");
            Console.WriteLine();

            int[,] result = Rotate90DegreesInPlace(input);
            Display(result);

            Console.Read();
        }
        
        /// <summary>
        /// First approach: Using temporal matrix
        /// Usage: MxN & NxN
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        public static int[,] Rotate90Degrees(int[,] input)
        {
            int m = input.GetLength(0);
            int n = input.GetLength(1);

            int[,] result = new int[n, m];

            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    result[j, m - 1 - i] = input[i, j];
                }
            }

            return result;
        }

        /// <summary>
        /// Second approach: In-Place swapping values
        /// Usage: NxN
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        public static int[,] Rotate90DegreesSwapping(int[,] input)
        {
            int m = input.GetLength(0);
            int n = input.GetLength(1);

            for (int i = 0; i < m-2; i++)
            {
                for (int j = 0; j < n - 2; j++)
                {
                    int temp = input[i, j];
                    input[i, j] = input[n - j - 1, i];                           //top left
                    input[n - j - 1, i] = input[n - i - 1, m - j - 1];      //bottom left
                    input[n - i - 1, m - j - 1] = input[j, n - i - 1];            //bottom right
                    input[j, n - i - 1] = temp;                             //top right

                }
            }

            return input;
        }

        /// <summary>
        /// Third approach. In-Place using matrix transponse and reversing rows
        /// Usage: NxN  
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        public static int[,] Rotate90DegreesInPlace(int[,] input)
        {
            //TODO: Expand this approach for MxN

            int n = input.GetLength(0);
            int m = input.GetLength(1);

            //Transpose the matrix
            for (int i = 0; i < n-2; i++)
            {
                for (int j = i+1; j < m; j++)
                {
                    input[j, i] ^= input[i, j];
                    input[i, j] ^= input[j, i];
                    input[j, i] ^= input[i, j];
                }
                Display(input);
                Console.WriteLine();
            }

            //Reverse rows
            for (int i = 0; i < n; i++)
            {
                for (int j = 0, k=m-1; j < m/2; j++,k--)
                {
                    input[i, j] ^= input[i, k];
                    input[i, k] ^= input[i, j];
                    input[i, j] ^= input[i, k];
                }
            }

            return input;
        }

        private static void Display(int[,] input)
        {
            for (int i = 0; i <input.GetLength(0); i++)
            {
                for (int j = 0; j < input.GetLength(1); j++)
                {
                    Console.Write(" {0} ", input[i, j]);
                }
                Console.WriteLine();
            }
        }

        private static int[,] Initialize(int[,] input)
        {
            int count = 1;

            for (int i = 0; i < input.GetLength(0); i++)
            {
                for (int j = 0; j < input.GetLength(1); j++)
                {
                    input[i, j]=count++;
                }
                Console.WriteLine();
            }

            return input;
        }


    }
}
